package com.learn.algorlthm;

/**
 * @classname:
 * @Description:数组中的逆序对
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-14 10:50
 * 题目描述：
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中
 * 的逆序对的总数 P。
 */
public class Learn51 {

    private long cnt;
    private int[] tmp;

    public int inversePairs(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums,0, nums.length-1);
        return (int)cnt%1000000007;
    }

    private void mergeSort(int[] nums, int s, int e) {
        if (e-s < 1)
            return;

        int m = s + (e - s) / 2;

        mergeSort(nums, s, m);
        mergeSort(nums, m+1, e);

        merge(nums, s, m, e);
    }

    private void merge(int[] nums, int l, int m, int h) {
        int i = l, j = m + 1, k = l;
        while (i <= m || j <= h) {
            if (i > m)
                tmp[k] = nums[j++];
            else if (j > h)
                tmp[k] = nums[i++];
            else if (nums[i] < nums[j])
                tmp[k] = nums[i++];
            else {
                tmp[k] = nums[j++];
                this.cnt += m - i + 1;  // nums[i] >= nums[j]，说明 nums[i...mid] 都大于 nums[j]
            }
            k++;
        }
        for (k = l; k <= h; k++)
            nums[k] = tmp[k];
    }

}
